\chapter{Sistemi distribuiti}

Un sistema distribuito e formato da un insieme di processi distinti che
comunicano tra loro scambiandosi dei messaggi . Ogni processore (nodo) nel
sistema e dotato di una propria memoria privata e di un proprio clock. Non
esiste la memoria comune e, quindi, non esiste un concetto di stato globale.
Inoltre, poiché i clock non sono necessariamente sincronizzati tra loro, non
esiste un concetto di clock globale che permetta di associare un ordinamento
totale agli eventi.\\\\
La visione moderna e quella classica di sistema distribuito differiscono per la
scala con cui questi vengono considerati. Nella visione classica i sistemi
distribuiti erano pensati molto piccoli, una decina o al massimo un centinaio di
macchine mentre al giorno d'oggi in alcuni casi un numero basso di nodi
influisce negativamente sulle prestazioni del sistema (per esempio TOR,
P2P).\\\\
Un classico esempio di sistema distribuito è quello del {\bf “Message Passing”},
in cui due o più nodi comunicano tra di loro utilizzando determinati canali di
comunicazione. 
Sul processo di comunicazione si possono fare alcune assunzioni:
\begin{itemize}
\item Il sistema distribuito può essere o meno statico, nel primo caso il numero
dei nodi che compongono la rete può variare solo per dei guasti.
\item Il protocollo utilizzato per la comunicazione può garantire che il messaggio
venga sempre consegnato (ad esempio usando Socket Stream) o no (Socket
Datagram).
\item Il protocollo utilizzato per la comunicazione garantisce che il messaggio
venga consegnato senza errori tramite controlli di integrità, per esempio CRC.
\item Il protocollo utilizzato per la comunicazione può prevedere l'uso di una coda
FIFO per i messaggi oppure no. 
\item I canali di comunicazione possono essere {\bf HalfDuplex} o {\bf FullDuplex}.
\item Uso di una primitiva per l'invio o la ricezione del messaggio bloccanti.

\end{itemize}

\section {Topologie di Rete}

Per considerare le prestazioni di una rete dobbiamo considerare i seguenti
aspetti:
\begin {itemize}
\item {\bf Grado} di un nodo, ovvero il numero di archi collegati a quel nodo.
Fornisce un stima del costo nel realizzare la rete.
\item {\bf Diametro}, ovvero il numero massimo di archi da oltrepassare per
permettere a due nodi di comunicare. Fornisce una stima dell'efficienza del
processo di comunicazione all'interno della rete.
\item {\bf Taglio}, ovvero il numero minimo di nodi che bisogna cancellare per
poter impedire la comunicazione tra alcuni dei nodi rimanenti. Fornisce un'ottima stima della tolleranza ai
guasti della rete.
\end{itemize}

{\bf Una rete si può definire “buona” se ha una media dei gradi e un diametro bassi e un
taglio elevato}, ovvero ha un basso costo di realizzazione, la comunicazione tra i nodi è relativamente veloce 
e ha un'alta tolleranza ai guasti.

\subsection{Ring}
Nella rete Ring ogni nodo è collegato con il nodo che lo precede e quello
che lo segue. La rete è simmetrica e non c'è nessuna distinzione tra i nodi.
L'unico vantaggio offerto da questo tipo di rete è il basso costo nella
realizzazione, il grado è molto basso ma al contrario il diametro risulta essere
elevato e il taglio basso. 
\insertImage{0.2}{ring_network}{Topologia di rete Ring}

\subsection{Star}
Nella rete Star c'è un nodo centrale che opera da collegamento tra tutti gli
altri nodi. Solitamente i canali sono duplex e la rete è simmetrica ad eccezione
del nodo centrale.
Lo svantaggio di questa tipologia è la troppa delicatezza del centro-stella in quanto punto nevralgico
dell'intera struttura.
\insertImage{0.2}{star_network}{Topologia di rete a Stella}



\subsection{Connessione completa}
Topologia simmetrica in cui ogni nodo è connesso a tutti gli altri, per questo
il suo grado è $n-1$ e il diametro è 1. 
Per fare in modo che un nodo non sia più raggiungibile dagli altri bisogna tagliare n link, 
questo significa che il taglio della struttura è n.
\insertImage{1}{conn_completa.JPG}{Topologia di rete a connessione completa}



\subsection{Mesh e Toro}
Un altro tipo di topologia di rete è la {\bf Mesh}, un esempio di sistema
bidimensionale in cui i nodi sono connessi tra loro in modo da formare una
griglia. In questo modo tutti i nodi centrali hanno grado 4, mentre i nodi periferici
hanno grado 2 o 3. Per fare in modo che tutti i nodi abbiano grado 4
si possono unire gli estremi della mesh, ottendendo così un {\bf Toro}.
\insertImage{ 0.7}{Mesh_topology.jpg}{Topologia a Toro}
Il grado e il taglio della topologia così ottenuta sono pari a 4, mentre il diametro di un Toro con n nodi è
$\sqrt{n}$.\\\\
\subsection{Tree e Fat Tree}
La topologia {\bf tree} è una generalizzazione della topologia a star, ma in
questo caso è l'utente che sceglie il grado massimo, che corrisponde al numero
di figli di un nodo. Il diametro è $\log_{grado} n$ e il taglio è 1.\\\\
\insertImage{0.2}{tree_network}{Topologia di rete Tree}\\
Uno dei problemi di questa tipologia è che la radice tende ad essere attraversata da un
traffico maggiore rispetto agli altri nodi.
Una soluzione a questo problema è data dal cosiddetto {\bf Fat Tree}, realizzato
in modo tale che più ci si avvicina alla radice e più i canali sono duplicati e hanno a 
disposizione più banda.\\\\
\subsection {Hypercube}
Generalizzando a dimensioni superiori a 2 l'idea alla base della Mesh si
ottiene la topologia {\bf Hypercube}, dove grado, diametro e
taglio hanno tutte valore $\log_2 n$.\\
Un ultimo tipo di topologia è la {\bf Multistage} (o {\bf Banyan network}) che
viene usata per router e switch ad alte prestazioni.

\section {Algoritmo ADR}

ADR è l'acronimo di {\bf Adaptive Data Replication} ed è un algoritmo adattivo
di replicazione dei dati ideato nel 1997.\\\\
L'algoritmo nasce dal bisogno di condividere dei dati che richiedono
aggiornamenti all'interno di un sistema distribuito, quindi è necessario
replicare i dati al fine di poter gestire il numero di richieste senza
sovraccaricare un unico server.\\
Il fatto che esistano più copie dello stesso dato porta ad un problema noto con
il nome di {\bf read one write all}. In altre parole se si modifica un file in
realtà bisogna propagare i cambiamenti effettuati in tutte le copie del file in
questione per mantenere il sistema aggiornato.\\\\
Un numero grande di copie rende più efficaci le operazioni di lettura, mentre
per le operazioni di scrittura è conveniente avere un numero basso di copie
perché le modifiche effettuate su una andranno replicate su tutte le altre. 
Bisogna quindi trovare un giusto compromesso sul numero di copie e una
collocazione adatta di queste in modo tale da ottimizzare queste due
operazioni.\\\\
L'algoritmo ADR usa come struttura un albero statico senza radice,
come quello in figura.

\insertImage{1}{ADR_TREE.jpg}{Topologia ad Albero}

Viene posto un unico vincolo sulla posizione dei duplicati, ovvero i nodi che possiedono
una copia devono appartenere ad un sottografo connesso della rete.\\\\
Ogni intervallo di tempo T l'algoritmo esegue dei controlli:
\begin{itemize}
\item {\bf Test di espansione} per verificare se è necessario replicare una
risorsa.
\item {\bf Test di compressione} per verificare se si può eliminare un
replicato.
\item {\bf Test di scambio} che viene eseguito solamente nel caso in cui sia
rimasta solo una copia della risorsa.
\end{itemize}
Per effettuare il test di espasione si definisce l'insieme R come l'insieme di
tutti i nodi che detengono una copia della risorsa e l'insieme R$_{neighbour}$ come quei
nodi appartenenti ad R che hanno dei vicini che non vi appartengono. \\
Ogni nodo in R$_{neighbour}$ deve controllare il traffico dai nodi vicini non
appartenenti ad R, se il numero di richieste per operazioni di lettura provenienti
da un nodo risulta essere maggiore del numero di operazioni di scrittura
provenienti da tutti gli altri nodi il test di espansione ha successo e la
risorsa viene replicata e salvata nel nodo preso in considerazione.\\\\
Per effettuare il test di compressione si definisce l'insieme
R$_{fringe}$ come l'insieme di tutti i nodi foglie del sottografo indotto da R,
quindi R$_{fringe}$ conterrà tutti quei nodi appartenenti all'insieme R che hanno un solo vicino.\\
Se un nodo appartenente ad R$_{fringe}$ ha già effettuato il test di espansione e
lo ha superato con successo allora non esegue il test di compressione, comincerà
ad effettuarlo al giro successivo se continuerà ad avere un solo vicino
appartenente ad R.\\
Durante il test ogni nodo che appartiene a R$_{fringe}$ confronta il numero
di richieste di scrittura ricevute dal suo vicino appartenente ad R con il numero 
di richieste di lettura ricevute. Se il numero di richieste di scrittura supera quello
di richieste di lettura il test è superato e quindi il nodo che ha eseguito il test 
chiede al vicino appartenente a R di poter cancellare la copia della risorsa: 
se questi non ha a sua volta superato il test di compressione dà il consenso 
e il duplicato viene cancellato, altrimenti solo uno dei due nodi cancellerà la 
copia (ad esempio quello con identificativo maggiore) in modo da evitare di
perdere tutte le copie della risorsa.\\\\
Il test di scambio infine viene effettuato quando rimane un'unica copia della
risorsa e consiste nel confrontare, per ogni vicino del nodo che sto prendendo in considerazione,
il numero di richieste ricevute da quel vicino (x) con il numero di richieste ricevute da
tutti gli altri vicini (y). Se $x > y$ il nodo che effettua il test manda una
copia della risorsa al vicino n e gli dice che quella è l'unica copia rimasta,
poi elimina la sua copia.\\\\
L'algoritmo è ottimale in sistemi in cui i cambiamenti risultano lenti, infatti,
supponendo di applicare ADR ad un sistema statico in cui le richieste sono
sempre le stesse, la replicazione si modifica fino a che non diventa la soluzione
ottimale.\\\\
L'algoritmo funziona solo utilizzando delle strutture ad albero perché
altrimenti ci potrebbero essere problemi dovuti alla compressione ma sopratutto
al routing: potrebbero capitare casi in cui le stesse richieste fatte da
un nodo potrebbero essere instradate in maniera diversa, rendendo quindi
impossibile ottimizzare correttamente la replicazione. Con la topologia ad
albero invece il cammino che può seguire una richiesta è unico e quindi questi
problemi di ambiguità non si presentano.\\\\
Prendiamo in considerazione l'albero in figura, posizioniamo la risorsa nei
nodi 3, 7, 8 ed eseguiamo le seguenti operazioni:
\begin{itemize}
\item 6 Scrittura: provoca l'esecuzione di 3 richieste di scrittura, una sul
nodo 3 e due di propagazione su 7 e 8.
\item 2 Scrittura: provoca l'esecuzione di 3 richieste di scrittura, una sul
nodo 1 che inoltra il messaggio a 3 che effettivamente scrive e poi propaga la
richiesta a 7 e 8.
\item 4 Lettura: provoca l'esecuzione di 3 domande di lettura e poi 3 messaggi
per restituire il risultato al nodo
\item 5 Lettura: come sopra.
\end{itemize}

In questo esempio la soluzione ottimale sarebbe quella di avere la risorsa nel
nodo 2, vediamo come lo si raggiunge.\\\\
Raggiunto il tempo T si esegue il test di espansione, l'unico
idoneo ad eseguirlo è il nodo 3 e lo esegue sia sul nodo 1 che su 6. Il
risultato del test di espansione è la replicazione del dato nel nodo 1.\\\\
Una volta terminato il test di espansione viene eseguito il test di compressione
dai nodi 7 e 8. 3 rientra nell'insieme R$_{fringe}$ ma avendo già eseguito con
successo il primo allora non esegue il secondo. Entrambi i nodi presi in
considerazione passano il test, infatti vengono ricevute due richieste di
scrittura dal nodo 3 e 0 richieste di lettura dagli altri nodi, quindi
richiedono al nodo 3 di poter cancellare la risorsa, ricevono il consenso in quanto 3 non vuole
cancellare la propria copia e quindi eliminano la loro.\\\\
Il risultato ottenuto al tempo T è quindi un avvicinamento verso la replicazione
ottimale.
Al tempo 2T la risorsa verrà duplicata in 2 e cancellata da 3, quindi R = \{2,1\}, infine al
tempo 3T R = \{2\}, che coincide con la soluzione ottimale.

\section {Reti Overlay}
\subsection{Introduzione}

Una rete overlay è una struttura di comunicazione di alto livello che si
appoggia alla rete Internet (o comunque ad una rete fisica sottostante) e 
permette ad un numero elevato di peer di comunicare tra di loro.\\\\
Le reti overlay possono essere di due tipi:
\begin{itemize}
\item {\bf Strutturato}, dove la struttura è fissa e predeterminata.
\item {\bf Non strutturato }in cui la topologia assume delle configurazioni
casuali, che dipendono dalle scelte individuali dei peer che costituiscono la
rete stessa.
\end{itemize}

\section {File Sharing}
Un sistema P2P  è una rete overlay non strutturata, in cui la topologia si
adegua alle esigenze dei peer.\\
In un sistema di File Sharing il punto cruciale è la condivisione dei file, ogni
peer decide quali sono le risorse che condivide o verso quali nutre degli
interessi, per questo motivo è preferibile non imporre una tolopologia
strutturata.\\
I problemi dovuti a una rete di File Sharing sono:
\begin{itemize}
\item Dinamicità della topologia, quindi file non più disponibili o
impossibilità di avere un visione globale del sistema.
\item Scalabilità della rete
\item Problemi nella ricerca dei file, i normali algoritmi di visita non sono
utilizzabili poiché la rete è molto dinamica e la ricerca risulterebbe più lenta rispetto alla
velocità di cambiamento della rete. 
\end{itemize}

\subsection {Ricerca in una rete P2P}
Il problema della ricerca in un sistema P2P si risolve con il {\bf Flooding}, dove un
peer richiede il file utilizzando tutti i canali di comunicazione che ha a
disposizione. Se la ricerca non ha successo allora le richieste vengono
propagate nel medesimo modo. Così facendo si utilizza in maniera pessima la banda a
disposizione, ma si ottimizzano i tempi di attesa.\\
E' da notare che se un peer inoltra la propria richiesta ai propri vicini e solo
un sottoinsieme di questi detiene la risorsa, gli altri continuano a
inoltrare la richiesta anche se questa è già stata soddisfatta, per questo
motivo si introduce il {\bf TTL (Time To Live)}, numero di Hop massimi a cui
inoltrare la richiesta, una volta superato questo valore la richiesta non viene
più inoltrata. Inoltre ogni peer mantiene un riferimento delle richieste
soddisfatte, in questo modo la stessa richiesta verrà effettuata solo una volta. \\\\
Questa soluzione è stata implementata da {\bf GNUtella}.\\\\

\subsection{Affinamento del flooding}
Dall'utilizzo di GNUtella si è arrivati
alla conclusione che la maggior parte delle risposte veniva sempre data dal 10\%
dei peer, il restante erano Free-Rider, ovvero peer che non apportano risorse
alla rete ma le richiedono solamente.\\\\
Per questo motivo l'algoritmo di flooding è stato modificato, decidendo di etichettare i vari link
uscenti da un peer con la possibilità di ricevere una risposta dal link stesso
ed eventualmente si propagare la domanda in base alla stima calcolata dei
succesivi link uscenti. Rispetto al Flooding classico vi è una riduzione del
traffico ma bisogna scegliere in maniera accurata la probabilità di
propagazione, trovando un giusto compremesso.\\
L'idea di fondo è di avere una fase di apprendimento, in cui tutti i link
hanno la stessa percentuale, e ad ogni operazione effettuata si aggiornano le
etichette in base alle risposte ottenute dal link stesso.\\
Eventualmente è possibile eliminare alcuni link con percentuale bassa, in modo
tale da escludere eventuali {\bf Free-rider} che verranno poi sostituiti da peer
più efficienti.\\\\

\subsection {Filtro di Bloom}
Il {\bf Filtro di Bloom} viene utilizzato per calcolare le stime di probabilità
per etichettare i link in una rete P2P.\\
Questo filtro si basa su delle funzioni di Hash, il cui utilizzo permette di 
mappare un insieme più grande in uno più piccolo e maggiormente compatto.\\
Il {\bf Filtro di Bloom} realizza una impronta di una risorsa, come avviene con
una funzione di hashing solamente che in questo caso le dimensioni  sono
inferiori, anziché 128-256  bit ne utilizza 16 bit. Questa soluzione in un
HashTable aumenterebbe a dismisura il numero di collisioni.
Per questo, nel filtro di Bloom è implementato in maniera differente dall'hash tradizionale: è infatti composto da k funzioni di hash indipendenti $h_1(x), h_2(x), ..., h_k(x)$ che producono un valore con distribuzione di probabilità uniforme in $\left[1..m\right]$. Su ogni elemento dell'insieme di elementi da codificare si applicano le k funzioni di hash $z_k=h_k(x)$ e le zone di un bit vector B di indice $z_k$ vengono poste a 1. Può succedere che un bit sia messo a 1 più di una volta.\\\\
Questa struttura permette di memorizzare un numero di elementi variabili, si può utilizzare la stessa per tutti gli elementi perché il contenuto di questa è ottenuto mediante l'{OR bit a bit} tra le impronte di tutti gli elementi. Per verificare che un file y non appartenga all'insieme bisogna applicargli le funzioni e andare a guardare nelle posizioni di B date dal risultato di ognuna di queste funzioni: se almeno una è diversa da 1 allora l'elemento non è contenuto.\\
Non si può operare allo stesso modo per verificare l'appartenenza: infatti i valori 1 nelle posizioni cercate del bit vector possono essere dovuti ad altri file, quindi è possibile solo ipotizzare l'appartenenza ad un insieme con un certo margine di errore. In particolare la probabilità di avere un falso positivo è stimata in $P=(1-e^{\frac{kn}{m}})^k$, con k numero di funzioni, m lunghezza del vettore B e n numero di valori codificati.\\
Fissando uno o più di questi parametri è possibile ottimizzare gli altri per ottenere le prestazioni desiderate, di solito si fissano le dimensioni m e n e si lavora sul numero di chiavi: una rappresentazione ottimale si ha quando si ha un numero di uni e di zeri più o meno pari alla metà dei bit a disposizione. Per ottimizzare il filtro bisogna utilizzare un numero adeguato di funzioni di hash: una limitazione infatti sta nel fatto che maggiore sarà il numero di funzioni hash utilizzate prima si riempirà l'array, ma utilizzandone poche sarà più difficile disambiguare le collisioni.\\\\
Una variante del filtro di Bloom sono i cosiddetti {\bf Counting Bloom Filters}, in cui al posto di un bit-vector si usa un array di contatori che vengono incrementati ogni volta che una funzione di hash restituisce il loro valore. Questi contatori devono essere di dimensione sufficiente ad impedire che si abbia overflow.\\
In questo modo non si può fare niente per il problema dei falsi positivi, ma diventa possibile la cancellazione di un file, operazione che con un bit vector non era consentita.\\\\
Per una rete Flooding si può utilizzare quindi un Filtro di Bloom, infatti se il file non è contenuto nel filtro allora non si effettua la richiesta in quel nodo, in questo modo diminuisce l'utilizzo della banda.\\


\subsection{Gossiping}
Il {\bf Gossiping} è una ottimizzazione dell'uso di un Filtro di Bloom, in cui
vengono creati più filtri ognuno corrispondente ad una sottorete.\\In questo
modo il flooding viene diretto solamente nella sottorete dove è più probabile
trovare il file.


\section {Overlay Strutturati}

In un overlay non strutturato è molto facile fare attacchi di tipo DoS a causa
della ricerca basata su flooding. Si può invece realizzare un overlay
strutturato che dispone di meccanismi di ricerca efficienti. Un overlay
strutturato introduce però due problemi, uno dovuto alla distribuzione dei dati,
che limita la libertà dei peer perché devono mantenere delle risorse su cui non
hanno alcun interesse, e l'altro dovuto al routing.

\subsection {Chord} 
Un esempio di Overlay Strutturato è {\bf Chord} sviluppato come progetto di
ricerca presso il MIT.\\\\
In Chord la distribuzione dei dati avviene utilizzando il {\bf Consistent
Hashing}: viene generata un'impronta hash del file utilizzata poi per
distribuire equamente i file sui peer.\\
Il sistema ha bisogno di una fase di {\bf Boostrap} in cui viene realizzato un
sistema di grandi dimensioni. Dato che l'assegnazione dell'impronta hash si può
considerare pseudo-casuale avendo un numero di peer elevato a disposizione la
distribuzione dei file sarà omogenea.\\\\
La struttura utilizzata è di tipo {\bf Ring} in cui ogni peer è identificato da
un numero casuale a 128 bit (sempre generato con una funzione di hashing) e in
cui i peer sono disposti in ordine crescente di identificativo. 
La distribizione delle risorse avviene assegnando ad
ogni peer tutti quei file che hanno un impronta compresa tra l'identificatore
del peer stesso e di quello successivo. Per poter distribuire omogeneamente i
file occorre quindi che la differenza tra due peer sia più o meno uguale per
tutta la rete, e ciò è garantito dall'uso della funzione di hash per
l'assegnazione degli ID.
\insertImage {0.5}{chord_network.png} {Rete Chord con 16 peer messi in
evidenza}\\\\
In una struttura semplice a Ring il routing non sarebbe efficiente, infatti per
raggiungere un determinato peer sarebbe necessario percorrere tutti i suoi
precedessori. Per questo motivo vengono introdotte delle scorciatoie che 
permettono di raggiungere dei peer lontani nell'anello. La struttura contenente
questi link è detta {\bf Finger Table} e contiene una quantità di connessione
ausiliarie che cresce in modo logaritmico in base alla dimensione della rete.
\insertImage {0.5} {chord_finger.png} {Finger table di un nodo all'interno di
Chord}\\
Chord adotta un algoritmo di instradamento di tipo {\bf Greedy}, ossia viene calcolata
la distanza da percorrere sull'anello e si prende nella Finger Table il link
corrispondente alla più grande potenza di due minore della distanza da
percorrere. Una volta raggiunto il peer si possono nuovamente sfruttare delle
scorciatoie per effettuare l'instradamento, e in questo caso la nuova scorciatoia
percorsa avrà una potenza di 2 minore di quella precedente.\\
La complessità dell'instradamento è quindi O($\log_2(n)$) nel caso pessimo.\\\\
Usando una funzione di hash a 128 bit è consigliabile non superate i 2$^{64
}$peer, per problemi dovuti alla collisione.
\subsection {Problemi dovuti ad una rete dinamica}
Se un nuovo peer desidera entrare a far parte della rete, gli viene
associato un identificatore sempre tramite la funzione di hashing per poter
trovare poi una posizione all'interno dell'anello utilizzando la stessa
strategia usata per la ricerca di un file. Una volta trovato il peer
responsabile del file con identificatore uguale al suo dovrà chiedergli di
passargli una copia di tutti i file che sono ora di sua competenza.
Prima di essere effettivamente operativo dovrà costruire la sua finger table
cercando tutti i peer che gestiscono i file con identificatore a distanza potenza
di 2 da lui. Questa operazione richiede $\log_2 (n)$ ricerche, ognuna delle
quali costa $\log_2 (n)$ e quindi la complessità totale di questa costruzione è
$\log_2 (n)^2$.\\\\
Oltre all'aggiunta di un peer anche l'uscita di un peer dall'anello causa dei
problemi, infatti oltre a dover aggiornare tutte le Finger Table tutti i file
che erano gestiti dal peer devono essere assegnati al suo predecessore. Questo
può avvenire solamente se il nodo lascia la struttura con un preavviso, quindi
bisogna implementare un algoritmo per compensare il distaccamento improvviso di
un peer, effettuando una copia dei file nel predecessore.
In questo modo all'uscita del peer il nodo predecessore ha già una
copia dei file che questo possedeva e rimane solo da aggiornare la copia di
backup che possiede il peer che lo precede, in modo da poter mantenere la
capacità di sostenere il distacco improvviso di un peer.

\subsection {Realizzazione della Finger Table}
La realizzazione di una Finger Table per un peer che entra nel ring può avvenire
in maniera collaborativa, ovvero il uovo peer chiede agli altri peer la loro
Finger Table per crearsi la propria, riducendo così il costo di una singola
entry da $\log_2$(n) a 1 e quindi quella dell'intera tabella a $\log_2$(n). Dato
un nodo a distanza 2$^i$ la scorciatoia 2$^i$ del nodo corrisponderà alla
scorciatoia successiva per il nuovo peer. Questo meccanismo riduce la
complessità ma si presta ad errori e ad attacchi alla sicurezza della rete.
È stata quindi proposta un alternativa che consiste nel tollerare un'approssimazione 
delle potenze di due, quindi una volta che un peer entra nella rete
potrà ereditare la Finger Table del predecessore come approssimazione di una corretta.
Se il sistema è di grandi dimensioni (e lo è) allora questa approssimazione è accettabile. 
Ereditando la tabella il peer entra immediatamente a far parte della rete e quindi è subito
operativo, pur non effettuando in maniera immediata dei routing efficienti.
Potrà però, ovviamente, correggere la propria finger table nel tempo.\\\\
\subsection {Varianti di Finger Table}
Sono state studiate alcune varianti per la realizzazione di Finger Table in modo
tale da ottimizzare le prestazioni. Alcune possibili varianti sono:
\begin {itemize}
\item Base k > 2: si sostituisce la base 2 con k e si introducono k-1 entry per ogni esponente. In
questo modo, con un opportuna scelta di k, otteniamo un miglioramento nelle prestazioni della ricerca
a discapito di un maggiore spazio occupato dalla finger table.
\item Sostituzione della funzione di espansione nella tabella dei finger, per
esempio utilizzando la semi-sequenza di Fibonacci: in questo modo le scorciatoie
crescono più rapidamente che utilizzando la base 2 e torna utile per realizzare
sistemi più efficienti nel caso di continui aggiornamenti. Questa soluzione fa
un uso ottimale dei finger in base al numero di hop massimo che è possibile
percorrere.
\item Max Range base k: questa soluzione prevede di costruire la Finger Table
fissando il numero di hop massimi che si vuole effettuare per raggiungere un
peer e memorizzare k-1 elementi per ogni hop, scelti in modo che ogni elemento è
il peer a distanza minima che non può essere raggiunto usando solo gli elementi
precedenti con un numero massimo di hop pari al "blocco" in cui si trova. La
semi-sequenza di Fibonacci è un Max Range a base 2. Con questo metodo e un opportuna scelta di k si ha un
notevole risparmio di spazio ed anche un notevole miglioramento delle
prestazioni con il crescere della rete (ovviamente si parla di milioni di
peer).
\end{itemize}


\subsection{Versione ottimizzata}
Alcune modifiche di Chord raggiungono una complessità dell'ordine di
O($\displaystyle \frac{\log_2 (N)}{\log_2 (\log_2 (N))}$), quindi con valori
molto grandi di N è possibile ottenere dei vantaggi piuttosto significativi in
termini di prestazioni, rendendo però maggiormente complessi gli algoritmi e le
strutture dati utilizzate e per questo motivo non trova molte applicazioni.\\
Un semplice algoritmo che permette di raggiungere prestazioni simili si chiama
{\bf Neighbour of Neighbour} e prevede l'introduzione di una perturbazione
casuale in ogni Finger Table al fine di rendere non più indifferente la scelta
del cammino da seguire (con una normale Finger Table ogni cammino per un certo
nodo ha lo stesso costo di ogni altro se si assume di poter utilizzare un certo
valore di distanza una volta sola). A questo punto per instradare una richiesta
un peer si fa dire da ogni suo vicino qual'è la sua Finger Table per poi
decidere in base al percorso migliore possibile.\\
Questa cosa però comporta uno scambio di messaggi piuttosto sostenuto.
Si può ottimizzare decidendo di introdurre la perturbazione in modo pseudo-casuale
utilizzando ad esempio l'impronta hash dell'identificativo del peer piuttosto
che l'identificativo stesso (essendo ricavato da una funzione di hash anche lui
è pseudo-casuale).
Con questo accorgimento ogni peer potrà calcolare la Finger Table di ogni suo
vicino senza dover mandare messaggi e nel caso di uso dell'identificativo come
perturbatore potrà anche calcolare, con approssimazione sempre peggiore, le
Finger Table dei vicini dei vicini e così via, riducendo quindi la complessità
dell'algoritmo.\\
Dopo varie prove si è notato che il caso ottimale si ha usando Neighbour of
Neighbour a previsione 3 (il vicino del vicino del vicino) poiché un valore più
elevato di previsione rende troppo impreciso il calcolo delle Finger Table. Si è
anche notato che l'unione di questa tecnica con il Max Range (o qualunque altra
ottimizzazione della Finger Table) non porta alcun vantaggio e in alcuni casi
peggiora addirittura le prestazioni.